package 我的Java学习_算法基础.day_07;

/**
 * @author 挚爱之夕
 * @date 2021/8/19 - 08 - 19 - 14:32
 * @Description: 我的暑假Java学习.day_06
 * @Version: 1.0
 */
public class _105_双管齐下解决递归问题 {
    static int mod = 1007;
    public static void main(String[] args) {
        int n = 5;
        System.out.println(f(n));
    }

    /**
     * 小白上楼梯，正向非递归
     * @param n
     * @return
     */
    public static int f(int n){
        if(n<0) return 0;
        if(n==0||n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 4;
        int x1 = 1,x2 = 2,x3 = 4;
        for(int i=4;i<=n;i++){
            int x_1 = x1;
            x1=x2%mod;
            x2=x3%mod;
            x3=((x1+x2)%mod+x_1)%mod;//注意
        }
        return x3;
    }
}
